package com.example.design.leetcode.other;

import java.util.LinkedHashMap;
import java.util.Map;

//146. LRU 缓存（最近最少使用缓存）
// LRU（Least Recently Used）是一种常用的缓存替换算法，当缓存达到一定大小后，会淘汰最近最少使用的缓存项。
// 该算法用于实现缓存淘汰策略，以便在缓存满时，能够及时清理最少使用的缓存项。

public class Lru {
    /**
     * 容量
     */
    int cap;
    Map<Integer, Integer> cache =  new LinkedHashMap<>();

    public Lru(int capacity) {
        this.cap = capacity;
    }

    /**
     * 1,是否包含key
     * 2,将key设置为最近使用
     * 3,返回元素
     */
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        makeRecently(key);

        return cache.get(key);
    }

    /**
     * 1,是否存在该元素，存在覆盖，并将该key设置为最近使用
     * 2,若链表满了，删除最旧没使用的元素, 就是链表头部元素
     * 3,添加元素
     */
    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            cache.put(key, val);
            makeRecently(key);
            return;
        }

        if (cache.size() >= this.cap) {
            Integer oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }

        cache.put(key,val);
    }

    /**
     * 是当前key变为最近使用的key。实现逻辑就是先删除，再新增
     * @param key
     */
    private void makeRecently(int key) {
        Integer val = cache.get(key);
        cache.remove(key);
        cache.put(key,val);
    }


}